#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strsafe.h>
#include <stdbool.h>

#define MAX_PLACES 20
#define INF 65535

// 用户结构体
typedef struct User {
   char id[10];
   char password[10];
   int permissions; // 用户权限
} User;

typedef User SLTDataType;

// 单链表节点结构体
typedef struct SListNode {
   SLTDataType data;
   struct SListNode* next;
} SL;

// 校园场所结构体
typedef struct Place {
   char name[50];
   char code[10];
   char description[200];
} Place;

// 图的边结构体
typedef struct Edge {
   int dest;
   int weight;
   struct Edge* next;
} Edge;

// 图结构体
typedef struct Graph {
   Place places[MAX_PLACES];
   Edge* edges[MAX_PLACES];
   int numPlaces;
} Graph;

//函数声明
SL* CreateNode(SLTDataType x);//创建新节点
SL* SListPushBack(SL* phead, SLTDataType x);//后插
void SListErase(SL** pphead, SL* pos);//删除指定项
int SListFind(SL* phead, char id[], char password[]);//登录
void SListDestroy(SL** pphead);//销毁链表
void destroyGraph(Graph* g);//   销毁图
void freeEdgesOfVertex(Edge* edgeList);//销毁图的辅助函数
void initGraph(Graph* g);//初始化图
bool addPlace(Graph* g, const char* name, const char* code, const char* description);// 添加场所
bool createAndInsertEdge(Graph* g, int src, int dest, int length);//创建并插入边节点到对应顶点的边链表头部的函数
bool addEdge(Graph* g, int src, int dest, int length);//添加边
void queryPlaceInfo(Graph* g, int placeIndex);//查询场所信息
void dijkstra(Graph* g, int src, int dest);// Dijkstra算法查找最短路径
void setGraph(Graph* g);//  初始化图
bool login(SL* plist);//登录
bool deletePlace(Graph* g, const char* code);//删除场所
SL* registerUser(SL* phead);//注册新用户
bool modifyUser(SL* phead, const char* id, char* need, int* permissions);//修改用户信息
bool deleteUser(SL** phead, const char* id);//  删除用户
bool deleteEdge(Graph* g, int src, int dest);// 删除边
bool modifyEdge(Graph* g, int src, int dest, int newWeight);//修改边
void manageUsers(SL** userList);// 用户管理
void managePlaces(Graph* g);// 场所管理
void managePaths(Graph* g);//路径管理

//菜单
void Administrator(SL** plist, Graph* g);//管理员菜单
void menu();
void load();
void Admload();
void Editload();

// 创建新节点
SL* CreateNode(SLTDataType x) {
   SL* newnode = (SL*)malloc(sizeof(SL));
   if (newnode == NULL) {
       perror("内存分配失败");
       exit(EXIT_FAILURE);
   }
   newnode->data = x;
   newnode->next = NULL;
   return newnode;
}

// 后插
SL* SListPushBack(SL* phead, SLTDataType x) {
   SL* newnode = CreateNode(x);
   if (phead == NULL) {
       return newnode;
   }
   else {
       SL* tail = phead;
       while (tail->next != NULL) {
           tail = tail->next;
       }
       tail->next = newnode;
       return phead;
   }
}

// 删除指定项
void SListErase(SL** pphead, SL* pos) {
   if (*pphead == NULL || pos == NULL) return;
   SL* target = *pphead;
   SL* record = *pphead;
   while (target != pos) {
       record = target;
       target = target->next;
   }
   record->next = target->next;
   free(target);
}

// 查找用户
int SListFind(SL* phead, char id[], char password[]) {
   SL* cur = phead;
   while (cur != NULL) {
       if (strcmp(cur->data.id, id) == 0 && strcmp(cur->data.password, password) == 0) {
           printf("欢迎%s登录\n", cur->data.id);
           if (cur->data.permissions == 1) {
               return 1; // 管理员登录
           }
           return 2; // 普通用户登录
       }
       cur = cur->next;
   }
   return 0; // 登录失败
}

// 销毁链表
void SListDestroy(SL** pphead) {
   if (pphead == NULL) return;
   SL* cur = *pphead;
   while (cur) {
       SL* next = cur->next;
       free(cur);
       cur = next;
   }
   *pphead = NULL;
}

// 图初始化
void initGraph(Graph* g) {
   g->numPlaces = 0;
   for (int i = 0; i < MAX_PLACES; i++) {
       g->edges[i] = NULL;
   }
}

// 添加场所
bool addPlace(Graph* g, const char* name, const char* code, const char* description) {
   if (g->numPlaces < MAX_PLACES) {
       if (strlen(code) >= 10) {
           printf("场所代号过长，请重新输入符合规范的代号（长度小于10）。\n");
           return false;
       }
       strcpy_s(g->places[g->numPlaces].name, sizeof(g->places[g->numPlaces].name), name);
       strcpy_s(g->places[g->numPlaces].code, sizeof(g->places[g->numPlaces].code), code);
       strcpy_s(g->places[g->numPlaces].description, sizeof(g->places[g->numPlaces].description), description);
       g->numPlaces++;
       return true;
   }
   printf("场所数量已达上限，无法添加新场所。\n");
   return false;
}

// 创建并插入边节点到对应顶点的边链表头部的函数
bool createAndInsertEdge(Graph* g, int src, int dest, int length) {
   Edge* newEdge = (Edge*)malloc(sizeof(Edge));
   if (newEdge == NULL) {
       perror("内存分配失败");
       return false;
   }
   newEdge->dest = dest;
   newEdge->weight = length;
   newEdge->next = g->edges[src];
   g->edges[src] = newEdge;
   return true;
}

// 添加边
bool addEdge(Graph* g, int src, int dest, int length) {
   if (src < 0 || src >= MAX_PLACES || dest < 0 || dest >= MAX_PLACES) {
       printf("起点或终点索引超出范围，请重新输入。\n");
       return false;
   }
   // 创建从源顶点到目标顶点方向的边
   if (!createAndInsertEdge(g, src, dest, length)) {
       return false;
   }
   // 创建从目标顶点到源顶点方向的边
   if (!createAndInsertEdge(g, dest, src, length)) {
       return false;
   }
   return true;
}

// 查询场所信息
void queryPlaceInfo(Graph* g, int placeIndex) {
   if (placeIndex >= 0 && placeIndex < g->numPlaces) {
       printf("场所名称: %s\n", g->places[placeIndex].name);
       printf("场所代号: %s\n", g->places[placeIndex].code);
       printf("场所简介: %s\n", g->places[placeIndex].description);
   }
   else {
       printf("场所编号超出范围。\n");
   }
}

// Dijkstra算法查找最短路径
void dijkstra(Graph* g, int src, int dest) {
   int dist[MAX_PLACES];
   int visited[MAX_PLACES] = { 0 };
   int prev[MAX_PLACES];
   for (int i = 0; i < g->numPlaces; i++) {
       dist[i] = INF;
       prev[i] = -1;
   }
   dist[src] = 0;

   for (int i = 0; i < g->numPlaces; i++) {
       int minDist = INF, u = -1;
       for (int j = 0; j < g->numPlaces; j++) {
           if (!visited[j] && dist[j] < minDist) {
               u = j;
               minDist = dist[j];
           }
       }

       if (u == -1) break;

       visited[u] = 1;

       Edge* current = g->edges[u];
       while (current != NULL) {
           if (!visited[current->dest] && dist[u] + current->weight < dist[current->dest]) {
               dist[current->dest] = dist[u] + current->weight;
               prev[current->dest] = u;
           }
           current = current->next;
       }
   }

   if (dist[dest] == INF) {
       printf("没有从 %s 到 %s 的路径。\n", g->places[src].name, g->places[dest].name);
   }
   else {
       printf("从 %s 到 %s 的最短路径长度为 %d。\n", g->places[src].name, g->places[dest].name, dist[dest]);
       // 打印路径
       int stack[MAX_PLACES], top = -1;
       for (int at = dest; at != -1; at = prev[at]) {
           stack[++top] = at;
       }
       printf("路径: ");
       for (int i = top; i >= 0; i--) {
           printf("%s ", g->places[stack[i]].name);
           if (i > 0) printf("-> ");
       }
       printf("\n");
   }
}

// 设置图
void setGraph(Graph* g) {
   initGraph(g);
   addPlace(g, "图书馆", "LIB", "存放大量书籍的地方");
   addPlace(g, "B3教学楼", "B3", "计算机学院楼");
   addPlace(g, "C3教学楼", "C3", "日常上课的教学楼");
   addPlace(g, "北区饭堂", "NCT", "位于北区的学校饭堂");
   addPlace(g, "南区饭堂", "SCT", "位于南区的学校饭堂");
   addPlace(g, "教师饭堂", "TCT", "教师专属饭堂");
   addPlace(g, "宿舍", "DOR", "学生居住的宿舍楼");
   addPlace(g, "体育馆", "GYM", "用于举办大型活动，体育赛事的场所");
   addPlace(g, "仙溪湖", "LAKE", "美丽的仙溪湖");
   addPlace(g, "行政办公楼", "ADM", "作为学校行政管理的中心，负责日常的行政工作");
   addPlace(g, "档案馆", "ARC", "存放学校重要文档和档案的地方");
   // 添加边
   addEdge(g, 0, 1, 5);// 假设0是图书馆，1是B3教学楼
   addEdge(g, 0, 10, 2);
   addEdge(g, 0, 2, 5);
   addEdge(g, 1, 2, 10);
   addEdge(g, 2, 3, 4);
   addEdge(g, 2, 5, 6);
   addEdge(g, 2, 6, 10);
   addEdge(g, 2, 9, 2);
   addEdge(g, 3, 5, 4);
   addEdge(g, 3, 8, 24);
   addEdge(g, 5, 8, 20);
   addEdge(g, 6, 7, 12);
   addEdge(g, 6, 3, 4);
   addEdge(g, 6, 8, 24);
   addEdge(g, 8, 4, 10);
}

// 显示菜单
void menu() {
   printf("------------------------------------\n");
   printf("----------欢迎来到佛山大学----------\n");
   printf("----------1、进行登陆认证----------\n");
   printf("----------2、查询场所代号-----------\n");
   printf("----------3、查询场所信息-----------\n");
   printf("----------4、查询最佳路径-----------\n");
   printf("----------5、退出导游系统-----------\n");
   printf("----------6、使用管理权限-----------\n");
   printf("------------------------------------\n");
}

// 加载用户列表
void load() {
   printf("-----------------------\n");
   printf("--------欢迎使用-------\n");
   printf("--------1、登陆--------\n");
   printf("--------2、注册--------\n");
   printf("-----------------------\n");
}

void Admload() {
   printf("---------------------------\n");
   printf("--------欢迎您管理员-------\n");
   printf("--------1、用户管理--------\n");
   printf("--------2、场所管理--------\n");
   printf("--------3、路径管理--------\n");
   printf("--------4、退出功能--------\n");
   printf("---------------------------\n");
}

void Editload() {
   printf("---------------------------\n");
   printf("---------请选择功能--------\n");
   printf("--------1、增加信息--------\n");
   printf("--------2、修改信息--------\n");
   printf("--------3、删除信息--------\n");
   printf("--------4、退出功能--------\n");
   printf("---------------------------\n");
}

// 单独的登录功能函数
bool login(SL* plist) {
   char id[10], password[10];
   int adm = 0;
   printf("请输入id: ");
   scanf_s("%9s", id, (unsigned)_countof(id));
   printf("请输入密码: ");
   scanf_s("%9s", password, (unsigned)_countof(password));
   adm = SListFind(plist, id, password);
   if (adm == 1) {
       return true;
   }
   else if (adm == 0) {
       printf("登录失败，请重新检查输入是否正确!\n");
       return false;
   }
   return false;
}

// 单独的注册功能函数
SL* registerUser(SL* phead) {
   User newUser;
   printf("请输入id（长度不超过9个字符）: ");
   scanf_s("%9s", newUser.id, (unsigned)_countof(newUser.id));
   printf("请输入密码（长度不超过9个字符）: ");
   scanf_s("%9s", newUser.password, (unsigned)_countof(newUser.password));
   newUser.permissions = 0; // 默认为普通用户权限
   return SListPushBack(phead, newUser);
}

// 删除场所
bool deletePlace(Graph* g, const char* code) {
   for (int i = 0; i < g->numPlaces; i++) {
       if (strcmp(g->places[i].code, code) == 0) {
           // 将场所从场所列表中移除
           for (int j = i; j < g->numPlaces - 1; j++) {
               g->places[j] = g->places[j + 1];
               g->edges[j] = g->edges[j + 1];
           }
           g->numPlaces--;
           printf("场所删除成功！\n");
           return true;
       }
   }
   printf("场所不存在！\n");
   return false;
}

// 修改用户信息
bool modifyUser(SL* phead, const char* id, char* need, int* permissions) {
   SL* cur = phead;
   while (cur != NULL) {
       if (strcmp(cur->data.id, id) == 0) {
           if (strcmp(need, "password") == 0) {
               printf("请输入新密码（长度不超过9个字符）: ");
               scanf_s("%9s", cur->data.password, (unsigned)_countof(cur->data.password));
               printf("用户密码修改成功！\n");
               return true;
           }
           else if (strcmp(need, "permissions") == 0) {
               printf("请输入新权限（0或1）: ");
               scanf_s("%d", permissions);
               printf("用户信息修改成功！\n");
               return true;
           }
       }
       cur = cur->next;
   }
   printf("用户不存在！\n");
   return false;
}

// 删除用户
bool deleteUser(SL** phead, const char* id) {
   SL* cur = *phead;
   SL* prev = NULL;
   while (cur != NULL) {
       if (strcmp(cur->data.id, id) == 0) {
           if (prev) {
               prev->next = cur->next;
           }
           else {
               *phead = cur->next;
           }
           free(cur);
           printf("用户 %s 删除成功！\n", id);
           return true;
       }
       prev = cur;
       cur = cur->next;
   }
   printf("用户不存在！\n");
   return false;
}

// 删除边
bool deleteEdge(Graph* g, int src, int dest) {
   Edge* current = g->edges[src];
   Edge* previous = NULL;
   while (current != NULL) {
       if (current->dest == dest) {
           if (previous) {
               previous->next = current->next;
           }
           else {
               g->edges[src] = current->next;
           }
           free(current);
           printf("边删除成功！\n");
           return true;
       }
       previous = current;
       current = current->next;
   }
   printf("边不存在！\n");
   return false;
}

// 修改边信息
bool modifyEdge(Graph* g, int src, int dest, int newWeight) {
   Edge* current = g->edges[src];
   while (current != NULL) {
       if (current->dest == dest) {
           current->weight = newWeight;
           return true;
       }
       current = current->next;
   }
   printf("边不存在！\n");
   return false;
}

// 管理员 - 用户管理功能
void manageUsers(SL** userList) {
   int choice;
   do {
       Editload();
       printf("请选择您要使用的功能：");
       scanf_s("%d", &choice);

       switch (choice) {
       case 1: {
           *userList = registerUser(*userList);
           break;
       }
       case 2: {
           char id[10];
           char need[20];
           int permissions;
           printf("输入要修改的用户id: ");
           scanf_s("%9s", id, (unsigned)_countof(id));
           printf("请输入要修改的项目（password/type/permissions）: ");
           scanf_s("%19s", need, (unsigned)_countof(need));
           if (modifyUser(*userList, id, need, &permissions)) {
               if (strcmp(need, "permissions") == 0) {
                   SL* cur = *userList;
                   while (cur != NULL) {
                       if (strcmp(cur->data.id, id) == 0) {
                           cur->data.permissions = permissions;
                           break;
                       }
                       cur = cur->next;
                   }
               }
           }
           break;
       }
       case 3: {
           char id[10];
           printf("输入要删除的用户id: ");
           scanf_s("%9s", id, (unsigned)_countof(id));
           deleteUser(userList, id);
           break;
       }
       case 4: {
           printf("退出用户管理。\n");
           return;
       }
       default: {
           printf("无效的选择，请重新输入。\n");
           break;
       }
       }
   } while (1);
}

// 管理员 - 场所管理功能
void managePlaces(Graph* g) {
   int choice;
   do {
       Editload();
       printf("请选择您要使用的功能：");
       scanf_s("%d", &choice);

       switch (choice) {
       case 1: {
           char name[50], code[10], description[200];
           printf("输入场所名称: ");
           scanf_s("%49s", name, (unsigned)_countof(name));
           printf("输入场所代号: ");
           scanf_s("%9s", code, (unsigned)_countof(code));
           printf("输入场所描述: ");
           scanf_s("%199s", description, (unsigned)_countof(description));
           if (addPlace(g, name, code, description)) {
               // 可添加成功后的相关提示等逻辑，此处暂省略
           }
           break;
       }
       case 2: {
           char code[10], item[20];
           for (int i = 0; i < g->numPlaces; i++) {
               printf("%-12s %s\n", g->places[i].name, g->places[i].code);
           }
           printf("请输入要修改的场所代号: ");
           scanf_s("%9s", code, (unsigned)_countof(code));
           printf("请输入要修改的项（name/code/description）: ");
           scanf_s("%19s", item, (unsigned)_countof(item));
           for (int i = 0; i < g->numPlaces; i++) {
               if (strcmp(g->places[i].code, code) == 0) {
                   if (strcmp(item, "name") == 0) {
                       printf("请输入新的名称: ");
                       scanf_s("%49s", g->places[i].name, (unsigned)_countof(g->places[i].name));
                   }
                   else if (strcmp(item, "code") == 0) {
                       printf("请输入新的代号: ");
                       scanf_s("%9s", g->places[i].code, (unsigned)_countof(g->places[i].code));
                   }
                   else if (strcmp(item, "description") == 0) {
                       printf("请输入新的描述: ");
                       scanf_s("%199s", g->places[i].description, (unsigned)_countof(g->places[i].description));
                   }
                   else {
                       printf("无效的修改项。\n");
                   }
                   printf("场所信息修改成功！\n");
                   return;
               }
           }
           printf("场所不存在！\n");
           break;
       }
       case 3: {
           char code[10];
           for (int i = 0; i < g->numPlaces; i++) {
               printf("%-12s %s\n", g->places[i].name, g->places[i].code);
           }
           printf("输入要删除的场所代号: ");
           scanf_s("%9s", code, (unsigned)_countof(code));
           deletePlace(g, code);
           break;
       }
       case 4: {
           printf("退出场所管理。\n");
           return;
       }
       default: {
           printf("无效的选择，请重新输入。\n");
           break;
       }
       }
   } while (1);
}

// 管理员 - 路径管理功能
void managePaths(Graph* g) {
   int choice;
   do {
       Editload();
       printf("请选择您要使用的功能：");
       scanf_s("%d", &choice);

       for (int i = 0; i < g->numPlaces; i++) {//打印所有地点
           printf("序号：%d  %-15s %s\n", i, g->places[i].name, g->places[i].code);
       }

       switch (choice) {
       case 1: {
           int src, dest, length;
           printf("输入起点序号: ");
           scanf_s("%d", &src);
           printf("输入终点序号: ");
           scanf_s("%d", &dest);
           printf("输入路径长度: ");
           scanf_s("%d", &length);
           if (addEdge(g, src, dest, length)) {
               printf("路径添加成功！\n");
           }
           break;
       }
       case 2: {
           int src, dest, newWeight;
           printf("输入起点序号: ");
           scanf_s("%d", &src);
           printf("输入终点序号: ");
           scanf_s("%d", &dest);
           printf("输入新的路径长度: ");
           scanf_s("%d", &newWeight);
           if (modifyEdge(g, src, dest, newWeight))
           {
               printf("边信息修改成功！\n");
           }
           break;
       }
       case 3: {
           int src, dest;
           printf("输入起点序号: ");
           scanf_s("%d", &src);
           printf("输入终点序号: ");
           scanf_s("%d", &dest);
           deleteEdge(g, src, dest);
           break;
       }
       case 4: {
           printf("退出路径管理。\n");
           return;
       }
       default: {
           printf("无效的选择，请重新输入。\n");
           break;
       }
       }
   } while (1);
}

// 管理员功能
void Administrator(SL** plist, Graph* g) {
   int choice;
   do {
       Admload();
       printf("请选择您要使用的功能：");
       scanf_s("%d", &choice);

       switch (choice) {
       case 1: {
           manageUsers(plist);
           break;
       }
       case 2: {
           managePlaces(g);
           break;
       }
       case 3: {
           managePaths(g);
           break;
       }
       case 4: {
           printf("退出管理员功能。\n");
           return;
       }
       default: {
           printf("无效的选择，请重新输入。\n");
           break;
       }
       }
   } while (1);
}

// 释放图中某一顶点的边链表内存
void freeEdgesOfVertex(Edge* edgeList) {
   Edge* current = edgeList;
   Edge* next;
   while (current != NULL) {
       next = current->next;
       free(current);
       current = next;
   }
}

// 销毁整个图
void destroyGraph(Graph* g) {
   if (g == NULL) {
       return;
   }
   // 释放每个顶点对应的边链表内存
   for (int i = 0; i < MAX_PLACES; i++) {
       freeEdgesOfVertex(g->edges[i]);
   }
   // 释放图结构体本身占用的内存
   free(g);
}

// 主函数
int main() {
   Graph g;
   SL* plist = NULL; // 列表头指针初始化为NULL
   setGraph(&g);    // 设置图的初始状态

   int choice, srcIndex, destIndex;
   char placeCode[10];
   bool limit = false; // 管理员权限
   User adm;
   strcpy_s(adm.id, sizeof(adm.id), "adm123456");
   strcpy_s(adm.password, sizeof(adm.password), "adm123456");
   adm.permissions = 1;
   plist = SListPushBack(plist, adm);

   do {
       menu(); // 显示菜单
       printf("请选择您要使用的功能：");
       scanf_s("%d", &choice);

       switch (choice) {
       case 1: { // 用户登录和注册
           load();
           int loginChoice;
           printf("1. 登录\n2. 注册\n请选择：");
           scanf_s("%d", &loginChoice);

           if (loginChoice == 1) { // 用户登录
               limit = login(plist);
               if (limit) {
                   printf("您已获得管理员权限。\n");
               }
           }
           else if (loginChoice == 2) { // 用户注册
               plist = registerUser(plist);
           }
           break;
       }
       case 2: { // 查询场所代号
           for (int i = 0; i < g.numPlaces; i++) {
               printf("%-12s %s\n", g.places[i].name, g.places[i].code);
           }
           break;
       }
       case 3: { // 查询场所信息
           printf("输入场所代号: ");
           scanf_s("%9s", placeCode, (unsigned)_countof(placeCode));
           for (int i = 0; i < g.numPlaces; i++) {
               if (strcmp(g.places[i].code, placeCode) == 0) {
                   queryPlaceInfo(&g, i);
                   break;
               }
           }
           break;
       }
       case 4: { // 查询最佳路径
           printf("输入起点代号: ");
           scanf_s("%9s", placeCode, (unsigned)_countof(placeCode));
           srcIndex = -1;
           for (int i = 0; i < g.numPlaces; i++) {
               if (strcmp(g.places[i].code, placeCode) == 0) {
                   srcIndex = i;
                   break;
               }
           }
           printf("输入终点代号: ");
           scanf_s("%9s", placeCode, (unsigned)_countof(placeCode));
           destIndex = -1;
           for (int i = 0; i < g.numPlaces; i++) {
               if (strcmp(g.places[i].code, placeCode) == 0) {
                   destIndex = i;
                   break;
               }
           }
           if (srcIndex != -1 && destIndex != -1 && srcIndex != destIndex) {
               dijkstra(&g, srcIndex, destIndex);
           }
           else {
               printf("请重新确认起点和终点代码。\n");
           }
           break;
       }
       case 5: { // 退出系统
           SListDestroy(&plist); // 销毁用户列表
           printf("感谢使用，再见！\n");
           exit(0);
           break;
       }
       case 6: { // 使用管理权限
           if (limit) {
               Administrator(&plist, &g);
           }
           else {
               printf("您没有管理员权限。\n");
           }
           break;
       }
       default: {
           printf("无效的选择。\n");
           break;
       }
       }
   } while (1);

   SListDestroy(&plist); // 销毁链表
   destroyGraph(&g);
   return 0;
}